package offer;

import javax.security.auth.login.CredentialNotFoundException;

@FunctionalInterface
public interface DeleteDuplicates {
    ListNode deleteDuplicates(ListNode head);
}
class DeleteDuplicatesImpl1 implements DeleteDuplicates{

    @Override
    public ListNode deleteDuplicates(ListNode head) {
        // 平凡情况
        if(head == null){
            return null;
        }else if(head.next == null){
            return head;
        }
        ListNode dummy = new ListNode(Integer.MIN_VALUE), tail = dummy, fast = head.next, slow = head;
        // 尾插法
        while (fast != null){
            if(fast.val != slow.val){
                if(slow.next == fast){
                    // 插入
                    tail.next = slow;
                    tail = slow;
                }
                slow = fast;
            }
            fast = fast.next;
        }
        if(slow.next == null){
            tail.next = slow;
            tail = slow;
        }
        tail.next = null;
        return dummy.next;
    }
}
